import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 苏李涛
 * Date: 2024-08-19
 * Time: 16:52
 */

/**
 * 有效三角形的个数:
 *
 * 给定一个包含非负整数的数组 nums ，返回其中可以组成三角形三条边的三元组个数。
 *
 *
 *
 * 示例 1:
 *
 * 输入: nums = [2,2,3,4]
 * 输出: 3
 * 解释:有效的组合是:
 * 2,3,4 (使用第一个 2)
 * 2,3,4 (使用第二个 2)
 * 2,2,3
 * 示例 2:
 *
 * 输入: nums = [4,2,3,4]
 * 输出: 4
 */
public class Triangle {
    /**方法：
     用双指针和单调性找到满足条件的三元组
     */
    public int triangleNumber(int[] nums) {
        //排序
        Arrays.sort(nums);
        int ret = 0;

        for(int i = nums.length-1; i >= 2; i--){//固定最大的数
            //利用双指针和单调性找到满足条件的三元组
            int left = 0;
            int right = i-1;
            while(left < right) {
                if(nums[left] + nums[right] > nums[i]){
                    ret += right-left;
                    right--;
                }else {
                    left++;
                }
            }
        }

        return ret;
    }
}
